#define _CRT_SECURE_NO_WARNINGS	

#include<cstdio>
#include<stack>
using namespace std;

typedef struct Node
{
    int left;
    int right;
}Node;

int Partition(int arr[], int left, int right)
{
    int tmp = arr[left];
    while (left < right)
    {
        while (right > left && arr[right] >= tmp)
            right--;
        arr[left] = arr[right];
        while (right > left && arr[left] <= tmp)
            left++;
        arr[right] = arr[left];
    }
    arr[right] = tmp;

    return right;
}

void Quick_Sort_No_Recursion(int arr[], int len)
{
    std::stack<Node> st;
    st.push({ 0,len - 1 });

    while (!st.empty())
    {
        Node node = st.top();
        st.pop();
        int par = Partition(arr, node.left, node.right);

        if (node.right > par + 1)
            st.push({ par + 1, node.right });
        if (node.left < par - 1)
            st.push({ node.left,par - 1 });
    }
}

int main()
{
    int arr[] = { 8,4,7,6,0,1,8,2,5,10 };
    Quick_Sort_No_Recursion(arr, 10);
    for (int i = 0; i < 10; i++)
        printf("%d ", arr[i]);
    return 0;
}